#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
void Swap(int& a, int& b)
{
	if (a != b)
	{
		a = a ^ b;
		b = a ^ b;
		a = a ^ b;
	}
}
void AdjuestDown(int arr[], int parent,int len)
{
	int child = 2 * parent + 1;
	while (child < len)
	{
		if (child + 1 < len && arr[child + 1] > arr[child])
		{
			child++;
		}
		if (arr[child] > arr[parent])
		{
			Swap(arr[parent], arr[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
void Heap(int arr[],int len)
{
	//O(n)
	for (int i = (len - 2) / 2; i >= 0; i--)
	{
		AdjuestDown(arr,i,len);
	}
	int end = len - 1;
	int k = 3;
	//O(logn*k)
	/*while (end >=0 && k--)
	{
		Swap(arr[end], arr[0]);
		AdjuestDown(arr, 0, end);
		end--;
	}
	cout << arr[end + 1] << endl;*/
	while (end >= 0)
	{
		Swap(arr[end], arr[0]);
		AdjuestDown(arr, 0, end);
		end--;
	}
}

int main()
{
	int arr[] = { 1,2,2,54,21,4,7,23,14,18,29 };
	Heap(arr,sizeof(arr) / sizeof(int));
	for (auto n : arr)
	{
		cout << n << " ";
	}
	cout << endl;

	return 0;
}